package leetcode.algorithm;

/**
 * @author jiangwz
 * @create 2019/11/11.
 */
public class TreeHelper {

    // [5,3,6,2,4,null,8,1,null,null,null,7,9]
    // 0 1 3 7
    // 0 1 2 3
    public static TreeNode array2Tree(Integer[] arr) {
//        if (arr.length <= 0)
//            return null;
//        return createBSTByArray(arr, 0, new TreeNode(arr[0]));
        return createBinaryTreeByArray(arr, 0);
    }

//    public void preOrder(int index) {
//        if(arr == null || arr.length == 0) {
//            System.out.println("????????????????????????????");
//        }
//        System.out.println(arr[index]);
//        if((index * 2 + 1) < arr.length) {
//            preOrder(2 * index + 1 );
//        }
//        if((index * 2 + 2) < arr.length) {
//            preOrder(2 * index + 2);
//        }
//    }


    private static TreeNode createBinaryTreeByArray(Integer[] array, int index) {
        TreeNode tn = null;
        if (index < array.length) {
            Integer value = array[index];
            if (value == null) {
                return null;
            }
            tn = new TreeNode(value);
            tn.left = createBinaryTreeByArray(array, 2 * index + 1);
            tn.right = createBinaryTreeByArray(array, 2 * index + 2);
            return tn;
        }
        return tn;
    }

    public static TreeNode createBSTByArray(Integer[] arr, int level, TreeNode root) {
        if (root == null) {
            return null;
        }
        int leftIndex = (int) Math.pow(2, level + 1) - 1;
        int rightIndex = (int) Math.pow(2, level + 1);
        if (leftIndex < arr.length)
            root.left = arr[leftIndex] == null ? null : new TreeNode(arr[leftIndex]);
        if (rightIndex < arr.length)
            root.right = arr[rightIndex] == null ? null : new TreeNode(arr[rightIndex]);
        if (root.left != null)
            createBSTByArray(arr, level + 1, root.left);
        if (root.right != null) {
            createBSTByArray(arr, level + 1, root.right);
        }
        return root;

    }

    public static void main(String[] args) {

        System.out.println(Math.pow(1, 2));
        System.out.println(Math.pow(2, 2));
        System.out.println(Math.pow(2, 3));
        System.out.println(Math.pow(3, 2));
        System.out.println(Math.pow(4, 2));
    }

}
